#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SP_NUM 256
#define RESULT_NUM 5

typedef struct 
{
    char name[256];
    int  value;
} spInfo;

spInfo spList[MAX_SP_NUM];

int results[RESULT_NUM][MAX_SP_NUM + 1];
int tmp_result[MAX_SP_NUM];
int results_index = 0;
int best_results = 0;
int EXPECT_REMAIN = 0;

void trim(char* strIn, char* strOut) // support in-place opreation
{
    char *a=strIn, *b;
    while (*a == ' '||*a == '\n' || *a == '\t') a++; // ignore spaces at the beginning
    b = strIn + strlen(strIn) - 1; // get pointer pointing at the end of the line
    while (*b == ' '||*b == '\n' || *a == '\t') b--; // ignore spaces at the end
    while (a<=b) *strOut++ = *a++; // transplace
    *strOut='\0';
}

void update_plan(int tot_sp, int now_sp_index, int now_credit, int results_index)
{
    //write results, without meaningless data in tmp_results (from previous one)
    for (int p = 0; p<= now_sp_index - 1; p++ ) results[results_index][p] = tmp_result[p];
    //set zero(cause there might be data from previous one)
    for (int p = now_sp_index; p< tot_sp; p++) results[results_index][p]=0;
    //the last place is for now_credit
    results[results_index][MAX_SP_NUM] = now_credit;
}

void foo(int tot_sp,int now_sp_index, int now_credit)
{
    if (best_results == RESULT_NUM) return; //skip~
    if (now_credit <= EXPECT_REMAIN || now_sp_index == tot_sp ) 
    {
        if (now_credit == EXPECT_REMAIN) best_results++; 
        if (results_index < RESULT_NUM) //table 'results' is still unfilled
        {
            update_plan(tot_sp,now_sp_index,now_credit,results_index);
            results_index++;
        }
        else //find a place to insert
        {
            int max_remain_i = 0;
            for (int w=0; w < RESULT_NUM; w++) //find the resolution whose remain is the max;
            {
                if (results[w][MAX_SP_NUM] > results[max_remain_i][MAX_SP_NUM]) max_remain_i = w;
            } 
            if(now_credit<results[max_remain_i][MAX_SP_NUM]) //if current remain is less than the max remain
                update_plan(tot_sp,now_sp_index,now_credit,max_remain_i);
        }
        return;
    }

    for (int i = now_credit/spList[now_sp_index].value; i >=0 ; i--)
    {
        tmp_result[now_sp_index]=i;
        foo(tot_sp, now_sp_index+1, now_credit - spList[now_sp_index].value*i);
    }
}

int load_spList(const char* filePath)
{
    FILE *fp = fopen(filePath,"r");
    char sp_info_line[512];
    int item_cnt = 0;
    while(!feof(fp))
    {
        fgets(sp_info_line, sizeof(sp_info_line), fp);
        
        if (sp_info_line[0] =='\n') continue; // ignore empty lines

        char *src = sp_info_line;
        char *dst = spList[item_cnt].name;

        trim(sp_info_line, sp_info_line); // ignore line spaces

        while (*src != '=') *(dst++) = *(src++); // copy item name
        *dst = '\0';
        src++;

        while(*src == ' ' || *src == '\t') src++;
        spList[item_cnt].value = atoi(src);

        item_cnt++;
    }
    fclose(fp);
    return item_cnt;
}

int benchmark(int m, int tot_sp, int flag_1, int flag_2, int flag_3)
{
    if (flag_1 == 1) EXPECT_REMAIN = m % 10; 
    if (flag_3 == 1 && flag_1 != 1) EXPECT_REMAIN = m % 2; 
    if (flag_2 == 1) EXPECT_REMAIN = m % spList[0].value;
    for (int i=1;i<m;i++)
    {   
        foo(tot_sp,0,i);
        printf ("credits: %8d, Bingo! \n",i); 
        
        results_index = 0;
        best_results = 0;
        memset(results, 0, sizeof(results));
        memset(tmp_result, 0, sizeof(tmp_result));
    }
}

int main()
{
    printf("# Items: \n");
    int tot_sp = load_spList("splist.txt");

    int flag_1 = 1; //assume all items are mutiples of 10
    int flag_2 = 1; //assume all items' values are totally equal 
    int flag_3 = 1; //assume all items' values are odd
    for (int i=0;i<tot_sp;i++)
    {
        printf("%5d | %s\n",spList[i].value,spList[i].name);
        
        if (spList[i].value%10 != 0) flag_1 = 0;
        if (i>0) if (spList[i].value != spList[i-1].value) flag_2 = 0;
        if (spList[i].value % 2 == 1) flag_3 = 0;
    }
    printf("# Total %d items;\n",tot_sp);
    
    int m;
    printf("# Please input the credits you've got: ");
    scanf("%d",&m);

    if (flag_1 == 1) EXPECT_REMAIN = m % 10; 
    if (flag_3 == 1 && flag_1 != 1) EXPECT_REMAIN = m % 2; 
    if (flag_2 == 1) EXPECT_REMAIN = m % spList[0].value;
    //if credits are not mutiples of 10 while all the items are,
    //then there's no possibility of all the credits being used up.
    
    //benchmark(m,tot_sp,flag_1,flag_2,flag_3); //

    foo(tot_sp,0,m); 
    printf("\n");

    //output results
    int cnt = 1; 
    for(int i = 0; i < results_index; i++)
    {
    	if(results[i][MAX_SP_NUM]==m) continue; //ignore when no credits used
        
        printf("# Plan %d:\n",cnt++);

        int remain = m;
        for (int j=0;j<tot_sp;j++) 
        {
            if (results[i][j] == 0) continue; //do not out put when getting none of it 
            printf("- %5d * %9d | %s\n",results[i][j],spList[j].value,spList[j].name);
            remain -= results[i][j] * spList[j].value;
        }
        //printf ("# Remain credits: %d\n", results[i][MAX_SP_NUM]);
        printf ("# Remain credits: %d\n",remain);
        printf("\n");
    }
    printf("# Finished!\n");
    if(cnt == 0) printf("# No solution can be found!\n");
    return 0;
}
